package 左哥算法.ch09贪心算法;

import org.junit.Test;
import 左哥算法.compare.贪心.Ch01Magic操作;
import 左哥算法.compare.贪心.Ch02括号深度;

import java.util.*;

public class Ch03一些贪心题目 {
    /**
     * ch01:力扣921. 使括号有效的最少添加
     */
    @Test
    public void ch01() {
        System.out.println(ch01Fun("(((()"));
    }

    /**
     * ch01思路
     * 1.首先要知道如何判别有效括号字符串.
     * 1.1如果出现过 左括号 比 右括号 少的情况,那该串一定不是一个有效括号
     * 1.2如果直到结尾, 左 括号 数量依然比右括号多,则该串也不是一个有效括号
     * 2.先判断有几处 1.1的情况.再判断结束之后 左括号比右括号多 多少个. 两者相加就是至少需要添加的括号
     */
    public int ch01Fun(String s) {
        char[] chars = s.toCharArray();
        int count = 0;    //待匹配的正括号数量
        int ans = 0;
        for (char c : chars) {
            if (c == '(') {
                count++;
            } else {
                if (count == 0) {  //情况1.1,右括号比左括号多
                    ans++;
                } else {
                    count--;
                }
            }
        }
        return count + ans;   //到结尾后 1.1 的个数,与左括号的个数相加
    }

    /**
     * Ch02：Magic操作，给你两个集合。
     * magic操作是将一个集合中的数移到另一个集合中，并保证两个集合的平均值都是上升的
     * 问，最多可以进行多少次magic操作
     */
    @Test
    public void ch02() {
        Integer[] arr1 = {25};   //
        Integer[] arr2 = {49, 37, 74, 43};
//        System.out.println(ch02Fun(arr1.clone(), arr2.clone()));
//        System.out.println(Ch01Magic操作.maxOps(arr1, arr2));
        Ch01Magic操作.compare(this::ch02Fun);
    }

    /**
     * ch02思路：
     * 对两个集合进行排序。
     * 找出这两个集合平均值。
     * 如果两个集合的平均值相等，则无法进行Magic操作。return 0
     * 如果一大一小，则从大集合中，取走所有符合要求的数。（有多少个这样的数，就有多少Magic操作）
     * 重复1，直到大集合中取不出符合要求的数.
     */
    public int ch02Fun(Integer[] arr1, Integer[] arr2) {
        double avg1 = avg(arr1);
        double avg2 = avg(arr2);
        if (avg1 == avg2) {
            return 0;
        }
        double maxAvg;
        double minAvg;
        Integer[] more = null, small = null;
        if (avg1 > avg2) {
            more = arr1;
            small = arr2;
            maxAvg = avg1;
            minAvg = avg2;
        } else {
            more = arr2;
            small = arr1;
            maxAvg = avg2;
            minAvg = avg1;
        }
        Arrays.sort(small);
        Arrays.sort(more);
        Set<Integer> smallSet = new HashSet<>(Arrays.asList(small));
        int ans = 0;
        int maxSize = more.length;
        for (int i = 0; i < more.length; i++) {
            if (more[i] > minAvg && more[i] < maxAvg && !smallSet.contains(more[i])) {
                minAvg += (more[i] - minAvg) / (smallSet.size() + 1);
                maxAvg = (maxAvg - 1.0 * more[i] / maxSize) * maxSize / (maxSize - 1);  //剔除一个数之后的平均数
                ans++;
                maxSize--;
                smallSet.add(more[i]);
            }
        }
        return ans;
    }

    public double avg(Integer... arr) {
        Integer sum = Arrays.stream(arr).reduce((res, o) -> res += o).get();
        return 1.0 * sum / arr.length;
    }

    public double avg(Collection<Integer> arr) {
        Integer sum = arr.stream().reduce((res, o) -> res += o).get();
        return 1.0 * sum / arr.size();
    }

    /**
     * ch03：给你一个合法的括号序列，要求计算括号的最大深度
     * 如 ((())) 深度为3
     */
    @Test
    public void ch03() {
        String str = "()((()))";
        System.out.println(ch03Fun(str));
        Ch02括号深度.compare(this::ch03Fun);
    }

    /**
     * 思路：
     * 如果判断是否有效括号：
     * 遇到左括号count+1
     * 遇到右括号count-1
     * 当count==0时，表示是一个有效括号。
     * 我们返回
     */
    public int ch03Fun(String s) {
        if (!isValid(s)){
            return 0;
        }
        char[] chars = s.toCharArray();
        int res = 0;
        int count = 0;
        for (char c : chars) {
            if (c == '(') {
                count++;
                res = Math.max(res, count);
            } else {
                count--;
            }
        }
        return res;
    }
    public boolean isValid(String s) {
        char[] chars = s.toCharArray();
        int count = 0;
        for (char c : chars) {
            if (c == '(') {
                count++;
            } else {
                count--;
            }
            if (count < 0) {
                return false;
            }
        }
        return count == 0;
    }

    /**
     * ch04:力扣517超级洗衣机
     * 有n台洗衣机，每台洗衣机中有一些衣服。
     * 每台洗衣机每轮可以向左或者扔出一件衣服。
     * 请问至少需要多少次操作，才能使得每个洗衣机衣服一样多？
     */
    @Test
    public void ch04(){
        int machines[] = {0,3,0};
        System.out.println(ch04Fun1(machines));
    }

    /**
     * ch04思路:
     *  先求一个平均值，然后求每个位置至少需要进行多少次操作。
     *  求每个位置的操作数，
     *      1.记录左侧和右侧多出来的衣服
     *      看该位置左侧的平均值与右侧衣服是否既不多也不少，表示需要在该位置进行0次操作。
     *      如果不等，则有两种情况：
     *          1.当前值>=平均值
     *              次数为：max(当前-平均值，max(左,右))
     *          2.当前值小于平均值
     *              次数为：max(左,右)-平均值
     * 所有位置中最大的操作数就是最终操作数。（因为该位置至少需要这么多次才能平衡）
     */
    public int ch04Fun1(int[] machines){
        int sum = Arrays.stream(machines).sum();
        if (sum % machines.length != 0) {
            return -1;
        }
        int avg=sum/machines.length;
        int res=Integer.MIN_VALUE;
        int pre=0;
        for (int i = 0; i < machines.length; i++) {
            int left=pre-i*avg; //左侧多出来的衣服
            int right=sum-pre-machines[i]-(machines.length-i-1)*avg;   //左侧多出来的衣服
            int count = 0;
            if (machines[i] > avg) {    //当前位置大于平均值
                count = Math.max(machines[i] - avg, Math.max(left,right));
            } else if (machines[i] < avg) { //当前位置小于平均值
                count = Math.max(left,right);
            }
            res=Math.max(res,count);
            pre+=machines[i];
        }
        return res;
    }
}
